Particle filter
)]] Particle filter methods, also known as Sequential Monte Carlo (SMC), are sophisticated model estimation techniques based on simulation. They are usually used to estimate Bayesian models and are the sequential ('on-line') analogue of Markov Chain Monte Carlo (MCMC) batch methods. Goal The particle filter aims to estimate the hidden parameters, \beta_k for k=0,1,2,3, \cdots , based only observed data y_k for k=0,1,2,3, \cdots . This method requires: * \beta_0, \beta_1, \cdots is a Markov process such that *: \beta_k|\beta_{k-1} \sim p_{\beta_k|\beta_{k-1}}(\beta|\beta_{k-1}) * y_0, y_1, \cdots are conditionally independent provided that \beta_0, \beta_1, \cdots are known *Each y_k only depends on \beta_k *: y_k|\beta_k \sim p_{y|\beta}(y|\beta_k) One example form of this scenario is : \beta_k = f(\beta_{k-1}) + w_k : y_k = h(\beta_k) + x_k where both w_k and x_k are independent and identitically distributed sequences with known probability density functions and f() & g() are known functions. These two equations can be viewed as state space equations and looks similar to the state space equations for the Kalman filter. "Direct version" algorithm The "direct version" algorithm is rather simple (compared to other particle filtering algorithms) and it uses composition and rejection. To generate a single sample \beta at k from p_{\beta_k|y_{1:k}}(\beta|y_{1:k}) : :1) Set p=1 :2) Uniformly generate L from P :3) Generate a test \hat{\beta} from its distribution p_{\beta_k|\beta_{k-1}}(\beta|\beta_{k-1|k-1}^{(L)}) :4) Generate the probability of \hat{y} using \hat{\beta} from p_{y|\beta}(y_k|\hat{\beta}) where y_k is the measured value :5) Generate another uniform u from m_k :6) Compare u and \hat{y} ::6a) If u is larger then repeat from step 2 ::6b) If u is smaller then save \hat{\beta} as \beta{k|k}^{(p)} and increment p :7) If p > P then quit The goal is to generate P "particles" at k using only the particles from k-1 . This requires that a Markov equation can be written (and computed) to generate a \beta_k based only upon \beta_{k-1} . This algorithm uses composition of the P particles from k-1 to generate a particle at k and repeats (steps 2-6) until P particles are generated at k . This can be more easily visualized if \beta is viewed as a two-dimensional array. One dimension is k and the other dimensions is the particle number. For example, \beta(k,L) would be the Lth particle at k and can also be written \beta_k^{(L)} (as done above in the algorithm). Step 3 generates a potential \beta_k based on a randomly chosen particle ( \beta_{k-1}^{(L)} ) at time k-1 and rejects or accepts it in step 6. In other words, the \beta_k values are generated using the previously generated \beta_{k-1} . Generally, this algorithm is repeated iteratively for a specific number of k values (call this N ). Initializing \beta_k=0|_{k=0} for all particles provides a starting place to generate \beta_1 , which can then be used to generate \beta_2 , which can be used to generate \beta_3 and so on up to k=N . When done, the mean of \beta_k over all the particles (or \frac{1}{P}\sum_{L=1}^P \beta_k^{(L)} ) is approximately the actual value of \beta_k . See also *Kalman filter References * Sequential Monte Carlo Methods in Practice, by A Doucet, N de Freitas and N Gordon. Published by Springer. * Tutorial on Particle Filters for On-line Nonlinear/Non-Gaussian Bayesian Tracking (2001); S. Arulampalam, S. Maskell, N. Gordon and T. Clapp; CiteSeer link Category:Techniques